package sorts;

public class MergeSort {

    public static void merge(int[] arr, int[] temp, int start, int end){
        int i = start;
        int j = (start + end)/2 + 1;
        int t = start;
        while(i <= (start + end)/2 && j <= end){
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                i++;
            } else {
                temp[t] = arr[j];
                j++;
            }
            t++;
        }
        while(i <= (start + end)/2){
            temp[t] = arr[i];
            i++;
            t++;
        }
        for(int a = start; a < t; a++){
            arr[a] = temp[a];
        }
    }

    public static void mergeSort(int[] arr, int[] temp, int start, int end){
        if(start < end){
            mergeSort(arr, temp, start, (start + end) / 2);
            mergeSort(arr, temp,(start + end) / 2 + 1, end );
            merge(arr, temp, start, end);
        }
    }

    public static void main(String[] args){
        int[] arr = new int[]{3,2,5,1,6,7,11,8};

        mergeSort(arr, new int[arr.length],0, arr.length -1);
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
    }
}
